# -*- coding: utf-8 -*-            
# @Time : 2022/10/31 22:01
# @Author  : lining
# @FileName: demo8.py
"""
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
中缀表达式求值
（2）带（）的表达式，先转成后缀表达式去计算。
[1]*/优先计算，+-后计算
s = " 2 - ( 1 * 2 + 2 ) * 2"   2 1 2 * 2  + 2 * -
s = " ( 1 + ( 4 + 5 + 2 ) - 3 ) + ( 6 + 8 ) "
2入数据栈,-入符号栈，（入符号栈，1入数据栈，*和栈顶比较，入符号栈，2入数据栈，+和栈顶比较，弹出*，再入符号栈，2入数据栈，
遇到）弹出符号栈栈顶，一直到（，*和栈顶比较，入符号栈，2入数据栈，没有了全部弹出
遇到数字，放到字符串后面，遇到运算符，先和栈顶运算符比较，如果是同级，先出栈顶运算，然后把当前运算符入栈，如果更高级
遇到（入栈，直到遇到）进行计算
"""

class Solution(object):
    def evalRPN(self, tokens):
        """
        :param tokens: 字符串类型，用空格分割
        :return:
        """
        # 存放运算符的栈
        stack_op = []
        # 存放后缀表达式
        stack_express = []
        token = tokens.strip().split(' ')
        for i in token:
            # 如果是数字就入栈
            if i.isdigit():
                stack_express.append(i)
                continue
            if i == '(':
                stack_op.append(i)
                continue
            # 遇到）的弹出栈顶，直到（
            if i == ')':
                a = stack_op.pop()
                while a != '(':
                    stack_express.append(a)
                    a = stack_op.pop()
                continue
            # 运算符先和栈顶运算符比较，栈顶等级高先计算栈顶然后把当前运算符入栈，当前比较高就直接入栈
            while stack_op and (self.compare_operate(i) <= self.compare_operate(stack_op[-1])):
                    op = stack_op.pop()
                    stack_express.append(op)
            stack_op.append(i)

        # 遍历完字符串，操作符栈还有内容把操作符都添加到字符串后面
        if len(stack_op) > 0:
            stack_op.reverse()
            stack_express.extend(stack_op)
        print(' '.join(stack_express))

    def compare_operate(self, op):
        """
        比较操作符优先级
        :return:
        """
        if op in ['+', '-']:
            return 1
        if op == '(':
            return 0
        return 2


s = " ( -1 + ( 4 + 5 + 2 ) - 3 ) + ( 6 + 8 ) "
Solution().evalRPN(s)
